package com.yubest;

/**
 * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
 *
 * 进阶：不要 使用任何内置的库函数，如  sqrt 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：num = 16
 * 输出：true
 * 示例 2：
 *
 * 输入：num = 14
 * 输出：false
 *  
 *
 * 提示：
 *
 * 1 <= num <= 2^31 - 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-perfect-square
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/4 9:10
 */
public class P0367 {

    public static void main(String[] args) {
        System.out.println(new Solution367().isPerfectSquare(16));

        System.out.println(45689 * 45689);
        System.out.println(new Solution367().isPerfectSquare(2087484721 + 1));
    }
}

class Solution367 {

    /**
     * 思路：二分查找
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        return isPerfectSquare(1, num / 2 + 1, num);
    }

    public boolean isPerfectSquare(int startNum, int endNum, long target) {
        if (startNum >= endNum) {
            return startNum * startNum == target;
        }
        long num = startNum + (endNum - startNum) / 2;
        long s = num * num;
        if (s > target) {
            return isPerfectSquare(startNum, (int) num, target);
        } else if (s < target) {
            return isPerfectSquare((int) num + 1, endNum, target);
        } else {
            return true;
        }
    }
}
